/**
 * Copyright (c) [2025] [何屹林]
 *
 * 保留所有权利。
 *
 * 文件名称：mindfa.cpp
 * 模块功能说明：
 * 该模块定义最小化DFA结构体，定义生成最小化DFA过程的各种函数，并构建最小化DFA状态转移表，完成了minDFA图的生成工作。
 *
 * 华南师范大学-计算机学院-网络工程-1班
 * 作者：何屹林-20222132023
 * 完成日期：2025年7月24日
 */
#include "logic.h"

QVector<MinDFANode*>minDFA;
int MDFAstart;

// 辅助函数：获取所有输入符号
QSet<QChar> getAllInputSymbols(const QVector<DFANode*>& nodes) {
    QSet<QChar> symbols;
    for (DFANode* node : nodes) {
        for (auto it = node->transfer.begin(); it != node->transfer.end(); ++it) {
            symbols.insert(it.key());
        }
    }
    return symbols;
}

// 辅助函数：查找状态所在分区索引
int findPartitionIndex(const QVector<QSet<int>>& partitions, int stateId) {
    for (int i = 0; i < partitions.size(); ++i) {
        if (partitions[i].contains(stateId)) {
            return i;
        }
    }
    return -1;  // 未找到
}



QVector<MinDFANode*> minimizeDFA(const QVector<DFANode*>& nodes) {
    if (nodes.empty()) return {};

    // 步骤1: 改进的初始划分（考虑flag和cd）
    QMap<QPair<QString, int>, QSet<int>> initialPartitionMap;
    for (DFANode* node : nodes) {
        int wordCode = node->flag.contains("o") ? node->cd : -1;
        initialPartitionMap[qMakePair(node->flag, wordCode)].insert(node->id);
    }

    QVector<QSet<int>> partitions;
    for (const auto& partition : initialPartitionMap) {
        partitions.append(partition);
    }

    // 步骤2: 使用更可靠的细分策略
    bool changed = true;
    while (changed) {
        changed = false;
        QVector<QSet<int>> newPartitions;

        for (const QSet<int>& P : partitions) {
            QMap<QString, QSet<int>> signatureGroups;

            // 生成完整签名（转移+属性）
            for (int stateId : P) {
                DFANode* node = nodes[stateId];
                QString signature;

                // 1. 添加状态属性
                signature += node->flag + "|" + QString::number(node->cd) + "|";

                // 2. 添加转移行为
                for (QChar ch : getAllInputSymbols(nodes)) {
                    if (node->transfer.contains(ch)) {
                        int target = node->transfer[ch];
                        bool found = false;
                        for (int i = 0; i < partitions.size(); ++i) {
                            if (partitions[i].contains(target)) {
                                signature += QString::number(i) + ",";
                                found = true;
                                break;
                            }
                        }
                        if (!found) signature += "-1,";
                    } else {
                        signature += "-1,";
                    }
                }

                signatureGroups[signature].insert(stateId);
            }

            // 处理细分结果
            if (signatureGroups.size() > 1) {
                changed = true;
                for (const auto& group : signatureGroups) {
                    newPartitions.append(group);
                }
            } else {
                newPartitions.append(P);
            }
        }

        partitions = newPartitions;
    }

    // 步骤3: 构建最小化DFA（确保不丢失节点）
    QVector<MinDFANode*> minDFA;
    QHash<int, int> stateToPartition; // 状态ID到分区ID的映射

    // 先建立映射关系
    for (int i = 0; i < partitions.size(); ++i) {
        for (int stateId : partitions[i]) {
            stateToPartition[stateId] = i;
        }
    }

    // 创建新节点
    for (int i = 0; i < partitions.size(); ++i) {
        MinDFANode* newNode = new MinDFANode(i);
        for (int stateId : partitions[i]) {
            newNode->addOriginalState(stateId, nodes);
        }
        minDFA.append(newNode);
    }

    // 步骤4: 精确建立转移关系
    for (MinDFANode* node : minDFA) {
        for (int stateId : node->originalStates) {
            DFANode* originalNode = nodes[stateId];
            for (auto it = originalNode->transfer.begin(); it != originalNode->transfer.end(); ++it) {
                int targetPartition = stateToPartition.value(it.value(), -1);
                if (targetPartition != -1) {
                    node->transfer[it.key()] = targetPartition;
                }
            }
        }
    }


    return minDFA;
}

void Logic::genMiniDFA()
{
    minDFA=minimizeDFA(nodes);
    QVector<QString> headers{ "状态", "ID", "单词内容", "单词编码" };
    int colCnt = headers.size();
    QMap<QChar, int> charCol;
    for (const auto& c : Chars) {
        if (C2S.contains(c))
            headers.push_back(trim(C2S[c]));
        else
            headers.push_back(c == ANY ? "ANY" : STR(c));
        charCol[c] = colCnt++;
    }
    int rowCnt = minDFA.size() + 1;
    MinDFATable.resize(rowCnt, QVector<QString>(colCnt));
    MinDFATable[0] = headers;
    int row = 1;
    for(auto&x:minDFA)
    {
        x->endcd=x->id;
        if(x->flag=="i")
        {
            MDFAstart=x->id;
        }
        MinDFATable[row][0] = x->flag;
        MinDFATable[row][1] = QString::number(x->id);
        QString token=Cd2Token[x->cd];
        MinDFATable[row][2] = x->cd > 0 ? token : "";
        MinDFATable[row][3] = x->cd > 0 ? QString::number(token_makecd[token]) : QString::number(x->endcd);

        if(x->cd>0)
        {
            x->endcd=token_makecd[Cd2Token[x->cd]];
            if(MainCd[0].contains(x->cd))
            {
                MainCd[0].append(x->endcd);
                MainCd[0].removeOne(x->cd);
            }
            if(MainCd[1].contains(x->cd))
            {
                MainCd[1].append(x->endcd);
                MainCd[1].removeOne(x->cd);
            }
        }
        else
        {
            x->endcd=0;
        }

        for(auto entry=x->transfer.begin();entry!=x->transfer.end();++entry)
        {
            MinDFATable[row][charCol[entry.key()]]=QString::number(entry.value());
        }
        ++row;
    }

}


//创建表格显示miniDFA
void Logic::MiniDFATableShow(const QString& title) {

    QStringList colHeader,header;
    for(int i=1;i<=MinDFATable.size();i++)
        colHeader.append(QString::number(i));

    for(int i=1;i<=MinDFATable[0].size();i++)
        header.append(QString::number(i));

    formShow(title,header,colHeader,MinDFATable);
    return;
}
